package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * arr
 * c
 * 1862. 向下取整数对和
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/31 10:28
 */
public class SumOfFlooredPairs {

    public static void main(String[] args) {
        SumOfFlooredPairs test = new SumOfFlooredPairs();

        // 10
//        int[] arr = {2, 5, 9};

        // 49
//        int[] arr = {7, 7, 7, 7, 7, 7, 7};

        // 139
//        int[] arr = {7, 14, 22, 27, 35, 42, 50, 63, 82, 98};

        //
        int[] arr = Utils.getArr(100000, 1, 10000);

        int i = test.sumOfFlooredPairs(arr);
        System.out.println(i);

    }

    public int sumOfFlooredPairs(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        int size = nums[length - 1] + 1;
        int[] arr = new int[size];
        for (int num : nums) {
            arr[num]++;
        }
        for (int i = 1; i < size; i++) {
            arr[i] += arr[i - 1];
        }
        long sum = 0;
        int last = -1;
        int max = arr[size - 1];
        for (int num : nums) {
            if (num == last) {
                continue;
            }
            last = num;
            int a = arr[num];
            int c = arr[num] - arr[num - 1];
            int b = 1;
            long item = c;
            int i = num - 1 + num;
            for (; i < size; i += num) {
                item = (item + b * (arr[i] - a)) % 1000000007;
                a = arr[i];
                b++;
            }
            item = item + (b * (max - a));
            sum = (sum + c * item) % 1000000007;
        }
        return (int) sum;
    }

}
